home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _triang.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  4.4 KB  |  144 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _triang.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /******************************************************************************
  18. *                                                                              *
  19. *  TRIANGULATE_PLANAR_MAP  (triangulation)                                     *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23. #include <LEDA/graph_alg.h>
  24.  
  25. #define NEXT_FACE_EDGE(e) G.cyclic_adj_pred(REV[e]) 
  26.  
  27. list<edge> TRIANGULATE_PLANAR_MAP(graph& G)
  28. { 
  29.  
  30. /* G is a planar map. This procedure triangulates all faces of G
  31.    without introducing multiple edges. The algorithm was suggested by 
  32.    Christian Uhrig and Torben Hagerup. 
  33.  
  34.    Description:
  35.  
  36.    Triangulating a planar graph G, i.e., adding edges
  37.    to G to obtain a chordal planar graph, in linear time:
  38.    
  39.    1) Compute a (combinatorial) embedding of G.
  40.    
  41.    2) Step through the vertices of G. For each vertex u,
  42.    triangulate those faces incident on u that have not
  43.    already been triangulated. For each vertex u, this
  44.    consists of the following:
  45.    
  46.      a) Mark the neighbours of u. During the processing
  47.    of u, a vertex will be marked exactly if it is a
  48.    neighbour of u.
  49.    
  50.      b) Process in any order those faces incident on u
  51.    that have not already been triangulated. For each such
  52.    face with boundary vertices u=x_1,...,x_n,
  53.         I)   If n=3, do nothing; otherwise
  54.         II)  If x_3 is not marked, add an edge {x_1,x_3},
  55.              mark x_3 and continue triangulating the face
  56.              with boundary vertices x_1,x_3,x_4,...,x_n.
  57.         III) If x_3 is marked, add an edge {x_2,x_4} and
  58.              continue triangulating the face with boundary
  59.              vertices x_1,x_2,x_4,x_5,...,x_n.
  60.    
  61.      c) Unmark the neighbours of x_1.
  62.    
  63.    Proof of correctness:
  64.    
  65.    A) All faces are triangulated.
  66.    This is rather obvious.
  67.    
  68.    B) There will be no multiple edges.
  69.    During the processing of a vertex u, the marks on
  70.    neighbours of u clearly prevent us from adding a multiple
  71.    edge with endpoint u. After the processing of u, such an
  72.    edge is not added because all faces incident on u have
  73.    been triangulated. This takes care of edges added in
  74.    step II).
  75.    Whenever an edge {x_2,x_4} is added in step III), the
  76.    presence of an edge {x_1,x_3} implies, by a topological
  77.    argument, that x_2 and x_4 are incident on exactly one
  78.    common face, namely the face currently being processed.
  79.    Hence we never add another edge {x_2,x_4}.
  80. */
  81.    
  82.   node v;
  83.   edge x;
  84.   list<edge> L;
  85.  
  86.   node_array<int>  marked(G,0);
  87.  
  88.   edge_array<edge> REV(G, 3*G.number_of_edges(), nil);
  89.  
  90.   if ( !compute_correspondence(G,REV)) 
  91.   error_handler(1,"TRIANGULATE_PLANAR_MAP: graph is not symmetric");
  92.  
  93.   forall_nodes(v,G)
  94.   {
  95.     list<edge> El = G.adj_edges(v);
  96.     edge e,e1,e2,e3;
  97.  
  98.     forall(e,El) marked[target(e)]=1;
  99.  
  100.     forall(e,El)
  101.     { 
  102.       e1 = e;
  103.       e2 = NEXT_FACE_EDGE(e1);
  104.       e3 = NEXT_FACE_EDGE(e2);
  105.  
  106.       while (target(e3) != v)
  107.       // e1,e2 and e3 are the first three edges in a clockwise 
  108.       // traversal of a face incident to v and t(e3) is not equal
  109.       // to v.
  110.        if ( !marked[target(e2)] )
  111.         { // we mark w and add the edge {v,w} inside F, i.e., after
  112.           // dart e1 at v and after dart e3 at w.
  113.  
  114.           marked[target(e2)] = 1;
  115.           L.append(x  = G.new_edge(e3,source(e1)));
  116.           L.append(e1 = G.new_edge(e1,source(e3)));
  117.           REV[x] = e1;
  118.           REV[e1] = x;
  119.           e2 = e3;
  120.           e3 = NEXT_FACE_EDGE(e2);
  121.         }
  122.         else
  123.         { // we add the edge {source(e2),target(e3)} inside F, i.e.,
  124.           // after dart e2 at source(e2) and before dart 
  125.           // reversal_of[e3] at target(e3).
  126.  
  127.           e3 = NEXT_FACE_EDGE(e3); 
  128.           L.append(x  = G.new_edge(e3,source(e2)));
  129.           L.append(e2 = G.new_edge(e2,source(e3)));
  130.           REV[x] = e2;
  131.           REV[e2] = x;
  132.         }
  133.      //end of while
  134.  
  135.     } //end of stepping through incident faces
  136.  
  137.    node w; forall_adj_nodes(w,v) marked[w] = 0;
  138.  
  139.   } // end of stepping through nodes
  140.  
  141. return L;
  142.  
  143. }
  144.